# 
# Move-to-front transformation to enhance compressibility
#
import copy

BYTE_ALPHABET = [chr(i) for i in range(256)]

def encode(str, alpha = None):
    if not alpha:
        alpha = BYTE_ALPHABET
    alpha = copy.copy(alpha)

    r = []
    for a in str:
        i = alpha.index(a)
        r.append(i)
        alpha = [alpha[i]] + alpha[:i] + alpha[i+1:]
    return r
        
def decode(str, alpha = None):
    if not alpha:
        alpha = BYTE_ALPHABET
    alpha = copy.copy(alpha)
    r = []
    
    for i in str:
        r.append(alpha[i])
        alpha = [alpha[i]] + alpha[:i] + alpha[i+1:]
    return r

if __name__ == '__main__':
    for i in ['aaaaabbbbb',
              'four score and seven years ago',
              'hello, world!']:
        e = encode(i)
        print e
        print decode(e)
